#pragma once
namespace Wang
{
	template<class T>
	struct Node
	{
		T _data;
		Node* _left;
		Node* _right;
		Node* _parent;
		int _bf;
		Node(const T& data)
			:_data(data)
			,_bf(0)
		{
			_left = _right = _parent = nullptr;
		}
	};

	template<class T>
	class avl
	{
	public:
		typedef Node<T> Node;
		bool insert(const T& data)
		{
			if (_root == nullptr)
			{
				_root = new Node(data);
				return true;
			}
			Node* pcur = _root;
			Node* parent = nullptr;
			while (pcur)
			{
				parent = pcur;

				if (data < pcur->_data)
					pcur = pcur->_left;
				else if (data > pcur->_data)
					pcur = pcur->_right;
				else
					return false;
			}
			pcur = new Node(data);
			if (data < parent->_data)
				parent->_left = pcur;
			else
				parent->_right = pcur;
			pcur->_parent = parent;
			while (parent)
			{
				if (parent->_left == pcur)
					parent->_bf--;
				else
					parent->_bf++;
				if (parent->_bf == 0)
					break;
				else if (parent->_bf == 1 || parent->_bf == -1)
				{
					pcur = parent;
					parent = pcur->_parent;
				}
				else
				{
					if (parent->_bf == 2 && pcur->_bf == 1)
					{
						RotateL(parent);
						pcur->_bf = parent->_bf = 0;
					}
					else if (parent->_bf == -2 && pcur->_bf == -1)
					{
						RotateR(parent);
						pcur->_bf = parent->_bf = 0;
					}
					else if (parent->_bf == 2 && pcur->_bf == -1)
					{
						if (pcur->_left->_bf == 0)
						{
							pcur->_bf = parent->_bf = 0;
						}
						else if (pcur->_left->_bf == 1)
						{
							parent->_bf = -1;
							pcur->_bf = 0;
							pcur->_left->_bf = 0;
						}
						else
						{
							parent->_bf = 0;
							pcur->_bf = 1;
							pcur->_left->_bf = 0;
						}
						RotateR(pcur);
						RotateL(parent);
					}
					else// -2 1
					{
						if (pcur->_right->_bf == 0)
						{
							parent->_bf = pcur->_bf = 0;
						}
						else if (pcur->_right->_bf == 1)
						{
							pcur->_bf = -1;
							parent->_bf = 0;
							pcur->_right->_bf = 0;
						}
						else
						{
							pcur->_bf = 0;
							parent->_bf = 1;
							pcur->_right->_bf = 0;
						}
						RotateL(pcur);
						RotateR(parent);
					}
					break;
				}
			}
			return true;
		}
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
		bool IsBalance()
		{
			return _IsBalance(_root);
		}
	private:
		bool _IsBalance(Node* root)
		{
			if (root == nullptr)
				return true;
			int le = High(root->_left);
			int ri = High(root->_right);
			if (abs(root->_bf) > 1)
				return false;	
			if (root->_bf != ri - le)
				return false;
			return _IsBalance(root->_left) && _IsBalance(root->_right);
		}
		int High(Node* root)
		{
			if (root == nullptr)
				return 0;
			int le = High(root->_left);
			int ri = High(root->_right);
			return (le > ri ? le : ri) + 1;
		}
		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;
			_InOrder(root->_left);
			cout << root->_data << ' ';
			_InOrder(root->_right);
		}
		void RotateL(Node* pcur)
		{
			Node* subR = pcur->_right;
			Node* subRL = subR->_left;

			pcur->_right = subRL;
			if (subRL)
				subRL->_parent = pcur;

			Node* parent = pcur->_parent;
			subR->_left = pcur;
			pcur->_parent = subR;

			subR->_parent = parent;
			if (parent)
			{
				if (parent->_left == pcur)
					parent->_left = subR;
				else
					parent->_right = subR;
			}
			else
			{
				subR->_parent = nullptr;
				_root = subR;
			}
		}

		void RotateR(Node* pcur)
		{
			Node* subL = pcur->_left;
			Node* subLR = subL->_right;

			pcur->_left = subLR;
			if (subLR)
				subLR->_parent = pcur;

			Node* parent = pcur->_parent;
			subL->_right = pcur;
			pcur->_parent = subL;

			subL->_parent = parent;
			if (parent)
			{
				if (parent->_left == pcur)
					parent->_left = subL;
				else
					parent->_right = subL;
			}
			else
			{
				_root = subL;
			}
		}
	private:
		Node* _root = nullptr;
	};
}